package main

import "fmt"

func main() {
	a := []int{1, 3}
	b := []int{2}
	fmt.Println(findMedianSortedArrays(a, b), float64(2))
}

// findMedianSortedArrays 找出两个有序数组中的中位数
// 以下称 nums1 为 A, nums2 为 B
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	// 中位数位置
	k := (m + n) / 2
	// 元素个数是否为偶数个
	isEven := (m+n)%2 == 0

	// A 与 B 比较的元素值下标
	var i, j int

	for k != 1 && m != 0 && n != 0 {
		if k/2 > m {
			i = m - 1
		} else {
			i = k/2 - 1
		}

		if k/2 > n {
			j = n - 1
		} else {
			j = k/2 - 1
		}

		if nums1[i] <= nums2[j] {
			k -= i + 1
			m -= i + 1
			nums1 = nums1[i+1:]
		} else {
			k -= j + 1
			n -= j + 1
			nums2 = nums2[j+1:]
		}
	}

	if m == 0 || n == 0 {
		if m == 0 {
			nums1, nums2 = nums2, nums1
		}

		if isEven {
			return float64(nums1[k]+nums1[k+1]) / 2
		} else {
			return float64(nums1[k])
		}
	}

	if isEven {
		if nums1[0] > nums2[0] {
			nums1, nums2 = nums2, nums1
		}

		if len(nums1) == 1 && nums1[1] < nums2[0] {
			return float64(nums1[0]+nums1[1]) / 2
		}

		return float64(nums1[0]+nums2[0]) / 2
	}

	return float64(min(nums1[0], nums2[0]))
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}
